#include <tool/libcell_subdivision.h>


typedef struct Sub_Poly_Ver {
    double* p;
    int i;
    double t;
}Sub_Poly_Ver;

static inline void sub_poly_ver_init(Sub_Poly_Ver* spv)
{
    spv->p = NULL;
    spv->i = 0;
    spv->t = 0;
}

//计算include angle
static inline  double compute_included_angle(double* a, double* b, double* n)
{
    normalize(a, 3); normalize(b, 3);
    double* n1 = out_product(a, b);
    double re = acos(inner_product(a, b, 3));
    if (inner_product(n1, n, 3) < 0)
    {
        re = 2 * M_PI - re;
    }
    free(n1);
    return re;
}

//点再边界是否是唯一的
static int vertex_is_only_one_on_bounds(Sub_Poly_Ver* spv, Sub_Poly_Ver** bounds, int len_bounds)
{
    int mark = 0;
    for (int i = 0; i < len_bounds; i++)
    {
        if (bounds[i] == spv)
        {
            mark++;
        }
    }
    if (mark == 1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
    return 1;
}
//判断边是否是inner_edge
//
static int vertex_is_in_inner_edges(Sub_Poly_Ver* spv1, Node* inner_edges)
{
    for (Node* nit = inner_edges; nit != NULL; nit = (Node*)(nit->Next))
    {
        Sub_Poly_Ver** temp = (Sub_Poly_Ver**)(nit->value);
        if (temp[0] == spv1 || temp[1] == spv1)
        {
            return 1;
        }
    }
    return 0;
}

static int edge_is_in_inner_edges(Sub_Poly_Ver* spv1,Sub_Poly_Ver* spv2, Node* inner_edges)
{
    for (Node* nit = inner_edges; nit != NULL; nit = (Node*)(nit->Next))
    {
        Sub_Poly_Ver** temp = (Sub_Poly_Ver**)(nit->value);
        if ((temp[0] == spv1&&temp[1]==spv2)||(temp[0] == spv2&&temp[1]==spv1) )
        {
            return 1;
        }
    }
    return 0;
}

static Node* inner_edges_remove(Sub_Poly_Ver* spv1,Sub_Poly_Ver* spv2, Node* inner_edges)
{
    for (Node* nit = inner_edges; nit != NULL; nit = (Node*)(nit->Next))
    {
        Sub_Poly_Ver** temp = (Sub_Poly_Ver**)(nit->value);
        if ((temp[0] == spv1&&temp[1]==spv2)||(temp[0] == spv2&&temp[1]==spv1) )
        {
            return node_remove(inner_edges,nit);
        }
    }
    return inner_edges;
}
static int is_line_intersecting_with_line_segment1(double* l, double* v1, double* v2)
{

    double d1[3] = { v1[0] - l[3],v1[1] - l[4],v1[2] - l[5] };
    double d2[3] = { v2[0] - l[3],v2[1] - l[4],v2[2] - l[5] };
    //double d3[3] = { v2[0]-v1[0],v2[1] - v1[1] ,v2[2] - v1[2] };
    //normalize(d3, 3);
    double* n1 = out_product(l, d1);
    double* n2 = out_product(l, d2);
    normalize(n1, 3); normalize(n2, 3);
    //printf("line intersect inner :%.17lf %lf\n", inner_product(n1, n2, 3),inner_product(l,d3,3));
    if (inner_product(n1, n2, 3) <= 0)
    {

        free(n1); free(n2);
        return 1;
    }
    free(n1); free(n2);
    return 0;
}
static inline int is_line_segment_intersecting_with_line_segment1(double* v1, double* v2, double* v3, double* v4)
{
    double l1[6] = { v2[0] - v1[0],v2[1] - v1[1],v2[2] - v1[2],v1[0],v1[1],v1[2] };
    double l2[6] = { v4[0] - v3[0],v4[1] - v3[1],v4[2] - v3[2],v3[0],v3[1],v3[2] };
    int re = 0;
    if (is_line_intersecting_with_line_segment1(l1, v3, v4) && is_line_intersecting_with_line_segment1(l2, v1, v2))
    {
        re = 1;
    }
    return re;
}


//判断和边界边是否相交，也要判断和inneredges是否相交
static int edge_is_intersect_with_bounds_edges(Sub_Poly_Ver* spv1, Sub_Poly_Ver* spv2,
    Sub_Poly_Ver** bounds, int len_bounds)
{
    for (int i = 0; i < len_bounds; i++)
    {
        if (bounds[i] == spv1 || bounds[(i + 1) % len_bounds] == spv1 ||
            bounds[i] == spv2 || bounds[(i + 1) % len_bounds] == spv2)
        {
            continue;
        }
        if (is_line_segment_intersecting_with_line_segment1(spv1->p, spv2->p,
            bounds[i]->p, bounds[(i + 1) % len_bounds]->p))
        {
            return 1;
        }
    }
    return 0;
}


static int edge_is_intersect_with_inner_edges(Sub_Poly_Ver* spv1,
    Sub_Poly_Ver* spv2, Node* inner_edges)
{
    for (Node* nit = inner_edges; nit != NULL; nit = (Node*)(nit->Next))
    {
        Sub_Poly_Ver** spvs = (Sub_Poly_Ver**)(nit->value);
        if (spvs[0] == spv1 || spvs[1] == spv1 || spvs[0] == spv2 || spvs[1] == spv2)
        {
            continue;
        }

        if (is_line_segment_intersecting_with_line_segment1(spv1->p, spv2->p,
            spvs[0]->p, spvs[1]->p))
        {
            return 1;
        }
    }
    return 0;
}

static Sub_Poly_Ver** update_boundry_and_inner_edges(Node** inner_edges, Sub_Poly_Ver** bounds,
    int len_bounds, int* len, Sub_Poly_Ver** temp)
{
    Node* n1 = NULL, * n2 = NULL;
    int mark[3] = { 0,-1,-1 };
    int flag = 0;
    for (int j = 0; j < len_bounds; j++)
    {
        flag = 0;
        for (int i = 0; i < 3; i++)
        {
            if (temp[i] == bounds[j] && temp[(i + 1) % 3] == bounds[(j + 1) % len_bounds])
            {
                mark[i] = 0;
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            n1 = node_pushback(n1, bounds[j]);
        }
    }
    flag = -1;
    for (int i = 0; i < 3; i++)
    {
        if (mark[i] == 0 && mark[(i + 1) % 3] == -1)
        {
            flag = i;
            break;
        }
    }
    n1 = node_reverse(n1);
    if (flag != -1)
    {
        for (Node* nit = n1; nit != NULL; nit = (Node*)(nit->Next))
        {
            if (nit->value == temp[(flag + 1) % 3])
            {
                for (int i = 0; i < 3; i++)
                {
                    if (mark[(flag + 1 + i)%3] == -1)
                    {
                        Node* node2 = (Node*)malloc(sizeof(Node));
                        Node_init(node2);
                        node2->value = temp[(flag + 2 + i) % 3];
                        node2->Next = nit;
                        if (nit->Prev != NULL)
                        {
                            node2->Prev = nit->Prev;
                            ((Node*)(nit->Prev))->Next = node2;
                        }
                        nit->Prev = node2;
                        nit = node2;
                    }
                }

                if (nit->Prev == NULL)
                {
                    n1 = nit;
                }

                break;
            }
        }
    }
    for (Node* nit = *inner_edges; nit != NULL; nit = (Node*)(nit->Next))
    {
        Sub_Poly_Ver** spvs = (Sub_Poly_Ver**)(nit->value);
        flag = 0;
        for (int i = 1; i < 3; i++)
        {
            if (temp[i] == spvs[0] && temp[(i + 1) % 3] == spvs[1])
            {
                flag = 1;
                SAFE_FREE(spvs);
                break;
            }
            else if (temp[i] == spvs[1] && temp[(i + 1) % 3] == spvs[0])
            {
                flag = 1;
                SAFE_FREE(spvs);
                break;
            }
        }
        if (flag == 0)
        {
            n2 = node_overlying(n2, spvs);
        }
        else
        {
            free(spvs);
        }
    }
    free_node(*inner_edges);
    *inner_edges = n2;
    *len = node_size(n1);
    int i = 0;
    Sub_Poly_Ver** re = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * (*len));
    for (Node* nit = n1; nit != NULL; nit = (Node*)(nit->Next))
    {
        re[i] = (Sub_Poly_Ver*)(nit->value);
        i++;
    }
    free_node(n1);
    return re;
}


static Int_RB_Tree* update_all_vertices(Sub_Poly_Ver** bounds, int len_bounds, Node* inner_edges)
{
    Int_RB_Tree* tree = (Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
    int_rb_tree_init(tree);

    for (int i = 0; i < len_bounds; i++)
    {
        tree->insert(tree, bounds[i]->i, bounds[i]);
    }
    for (Node* nit = inner_edges; nit != NULL; nit = (Node*)(nit->Next))
    {
        Sub_Poly_Ver** spvs = (Sub_Poly_Ver**)(nit->value);
        tree->insert(tree, spvs[0]->i, spvs[0]);
        tree->insert(tree, spvs[1]->i, spvs[1]);
    }

    return tree;
}

static inline int is_three_point_in_one_line(double* p1, double* p2, double* p3)
{
    double temp_p1[3] = { p2[0] - p1[0],p2[1] - p1[1],p2[2] - p1[2] };
    double temp_p2[3] = { p3[0] - p1[0],p3[1] - p1[1],p3[2] - p1[2] };
    double* p = NULL;
    //p = out_product(temp_p1, temp_p2);
   /* if (SAFE_SQRT(p[0] * p[0] + p[1] * p[1] + p[2] * p[2]) < 0)
    {
        printf("%.9lf\n", SAFE_SQRT(p[0] * p[0] + p[1] * p[1] + p[2] * p[2]));
        SAFE_FREE(p);
        return 1;
    }*/
    normalize(temp_p1, 3);
    normalize(temp_p2, 3);
    //normalize 
    p = out_product(temp_p1, temp_p2);
    int re = 0;
    if (fabs(p[0]) < 1e-5 && fabs(p[1]) < 1e-5 && fabs(p[2]) < 1e-5)
    {
        SAFE_FREE(p);
        return 1;
    }
    SAFE_FREE(p);
    return re;
}

static int vertex_is_in_bounds(Sub_Poly_Ver* spv, Sub_Poly_Ver** bounds, int len_bounds)
{
    for (int i = 0; i < len_bounds; i++)
    {
        if (bounds[i] == spv)
        {
            return 1;
        }
    }
    return 0;
}

static int is_triangle_legal(Sub_Poly_Ver* spv0, Sub_Poly_Ver* spv, Sub_Poly_Ver* spv1, double* normal)
{
    double dir1[3] = { spv1->p[0] - spv->p[0],spv1->p[1] - spv->p[1],spv1->p[2] - spv->p[2] };
    double dir2[3] = { spv0->p[0] - spv->p[0],spv0->p[1] - spv->p[1],spv0->p[2] - spv->p[2] };

    normalize(dir1, 3); normalize(dir2, 3);
    double* dir = out_product(dir1, dir2);
    if (inner_product(dir, normal, 3) < 1e-7)
    {
        SAFE_FREE(dir);
        return 0;
    }
    SAFE_FREE(dir);
    return 1;
}

static int is_triangle_legal1(Sub_Poly_Ver* spv0, Sub_Poly_Ver* spv, Sub_Poly_Ver* spv1, double* normal, Sub_Poly_Ver** bounds, int len_bounds)
{
    if (len_bounds <= 3)
    {
        return 1;
    }
    double** bounds1 = (double**)malloc(sizeof(double*)*(len_bounds-1));
    int k = 0;
    for (int i=0;i<len_bounds;i++)
    {
        if (bounds[i] == spv)
        {
            continue;
        }
        bounds1[k] = bounds[i]->p; k++;
    }
    double normal1[3]={0};
    compute_plane_normal_of_jordan_curve(bounds1,k,normal1);
    free(bounds1);
    if (inner_product(normal1, normal, 3) < 1e-5)
    {
        // SAFE_FREE(normal1);
        return 0;
    }
    // SAFE_FREE(normal1);
    
    return 1;
}

static int is_triangle_legal2(Sub_Poly_Ver* spv0, Sub_Poly_Ver* spv, Sub_Poly_Ver* spv1, double* normal, Int_RB_Tree* vs)
{
    for (auto it=vs->begin(vs);it.it!=NULL;it++)
    {
        if (it.second == spv0 || it.second == spv || it.second == spv1)
        {
            continue;
        }
        Sub_Poly_Ver* spv2 = (Sub_Poly_Ver*)(it.second);

        if (is_triangle_legal(spv2,spv0,spv,normal)&& is_triangle_legal(spv2, spv, spv1, normal)&& is_triangle_legal(spv2, spv1, spv0, normal))
        {
            return 0;
        }
      
    }

    return 1;
}


static Sub_Poly_Ver** attemp_to_get_triangle(Int_RB_Tree* vs, Sub_Poly_Ver* spv0, Sub_Poly_Ver* spv,
    Sub_Poly_Ver* spv1, Sub_Poly_Ver* spv2, Sub_Poly_Ver** bounds, int len_bounds, Node* inner_edges, double* normal)
{
    Sub_Poly_Ver** re = NULL;
    for (auto it = vs->begin(vs); it.it != NULL; it++)
    {
        Sub_Poly_Ver* spv3 = (Sub_Poly_Ver*)(it.second);
        if (!vertex_is_in_bounds(spv3, bounds, len_bounds))
        {
            if (is_triangle_legal(spv, spv1, spv3, normal) &&is_triangle_legal2(spv, spv1, spv3, normal,vs)&& !edge_is_intersect_with_bounds_edges(spv, spv3,
                bounds, len_bounds) && !edge_is_intersect_with_inner_edges(spv, spv3, inner_edges)
                && !edge_is_intersect_with_bounds_edges(spv1, spv3,
                    bounds, len_bounds) && !edge_is_intersect_with_inner_edges(spv1, spv3, inner_edges)
                )
            {
                re = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * 3);
                re[0] = spv; re[1] = spv1; re[2] = spv3;
                return re;
            }
        }
    }

    if (is_triangle_legal(spv, spv1, spv2, normal)&&is_triangle_legal1(spv,spv1,spv2,normal,bounds, len_bounds)
        && is_triangle_legal2(spv, spv1, spv2, normal,vs)&&!edge_is_intersect_with_bounds_edges(spv, spv2,
            bounds, len_bounds) && !edge_is_intersect_with_inner_edges(spv, spv2, inner_edges))
    {
        re = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * 3);
        re[0] = spv; re[1] = spv1; re[2] = spv2;
        return re;
    }

    if (is_triangle_legal(spv0, spv, spv1, normal) && is_triangle_legal1(spv0, spv, spv1, normal, bounds, len_bounds)
        && is_triangle_legal2(spv0, spv, spv1, normal,vs)  &&!edge_is_intersect_with_bounds_edges(spv0, spv1,
            bounds, len_bounds) && !edge_is_intersect_with_inner_edges(spv0, spv1, inner_edges))
    {
        re = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * 3);
        re[0] = spv0; re[1] = spv; re[2] = spv1;
        return re;
    }

    return NULL;
}


void subdivision_of_polygon_with_edges(Int_RB_Tree* vs, Sub_Poly_Ver** bounds, int len_bounds,
    Node* inner_edges, Node** tris, double* normal)
{
    if ((vs->size <= 3 || len_bounds <= 3) && inner_edges == NULL)
    {
        Sub_Poly_Ver** spvs = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * 3);
        spvs[0] = bounds[0]; spvs[1] = bounds[1]; spvs[2] = bounds[2];
        *tris = node_overlying(*tris, spvs);
        return;
    }
    Sub_Poly_Ver** temp = NULL;
    Sub_Poly_Ver* spv = NULL, * spv0 = NULL, * spv1 = NULL, * spv2 = NULL;
    for (int i = 0; i < len_bounds; i++)
    {
        spv0 = bounds[(i - 1 + len_bounds) % len_bounds];
        spv1 = bounds[(i + 1 + len_bounds) % len_bounds];
        spv2 = bounds[(i + 2 + len_bounds) % len_bounds];
        spv = bounds[i];
        temp = attemp_to_get_triangle(vs, spv0, spv, spv1, spv2, bounds, len_bounds, inner_edges, normal);
        if (temp == NULL)
        {
            continue;
        }
        else
        {
            break;
        }
    }
    if (temp == NULL)
    {
        return;
    }

    *tris = node_overlying(*tris, temp);
    int len_bounds1;
    Sub_Poly_Ver** bounds1 = update_boundry_and_inner_edges(&inner_edges, bounds, len_bounds, &len_bounds1, temp);

    Int_RB_Tree* vs1 = update_all_vertices(bounds1, len_bounds1, inner_edges);


    subdivision_of_polygon_with_edges(vs1, bounds1, len_bounds1, inner_edges, tris, normal);

    int_rb_tree_free(vs1);
    SAFE_FREE(bounds1);

}

typedef struct Fusion_Inner_Edges {
    Node* vs;
    Sub_Poly_Ver** lines;
    int* marks;
    int len;
    int is_loop;

}Fusion_Inner_Edges;

static Node* fusion_inner_edges_to_lines(Node* inner_edges)
{
    Node* re = NULL;
    // for (Node* nit1 = inner_edges; nit1 != NULL; nit1 = (Node*)(nit1->Next))
    // {
    //     Sub_Poly_Ver** spvs = (Sub_Poly_Ver**)(nit1->value);
    // }
    Node* inner_edges1 = node_copy(inner_edges);
    while (inner_edges1 != NULL)
    {
        Sub_Poly_Ver** temp1 = (Sub_Poly_Ver**)(inner_edges1->value);
        Fusion_Inner_Edges* fie = (Fusion_Inner_Edges*)malloc(sizeof(Fusion_Inner_Edges));
        fie->vs = NULL;
        fie->vs = node_overlying(fie->vs, temp1[0]);
        fie->vs = node_overlying(fie->vs, temp1[1]);
        fie->is_loop = 0; fie->lines = NULL; fie->len = 0; fie->marks = NULL;
        re = node_overlying(re, fie);
        inner_edges1 = node_remove(inner_edges1, inner_edges1);

        int flag = 1;
        while (flag)
        {
            flag = 0;
            Sub_Poly_Ver* spv1 = (Sub_Poly_Ver*)(fie->vs->value);
            Sub_Poly_Ver* spv2 = (Sub_Poly_Ver*)(node_reverse(fie->vs)->value);
            for (Node* nit = inner_edges1; nit != NULL; nit = (Node*)(nit->Next))
            {
                Sub_Poly_Ver** temp = (Sub_Poly_Ver**)(nit->value);
                if (temp[0] == spv1)
                {
                    fie->vs = node_overlying(fie->vs, temp[1]);
                    flag = 1;
                }
                else if (temp[1] == spv1)
                {
                    fie->vs = node_overlying(fie->vs, temp[0]);
                    flag = 1;
                }
                else if (temp[0] == spv2)
                {
                    node_pushback(node_reverse(fie->vs), temp[1]);
                    flag = 1;
                }
                else if (temp[1] == spv2)
                {
                    node_pushback(node_reverse(fie->vs), temp[0]);
                    flag = 1;
                }
                if (flag)
                {
                    inner_edges1 = node_remove(inner_edges1, nit);
                    break;
                }
            }
        }
    }

    for (Node* nit = re; nit != NULL; nit = (Node*)(nit->Next))
    {
        Fusion_Inner_Edges* fie = (Fusion_Inner_Edges*)(nit->value);
        fie->len = node_size(fie->vs);
        fie->lines = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * fie->len);
        fie->marks = (int*)malloc(sizeof(int) * fie->len);
        memset(fie->marks, 0, sizeof(int) * fie->len);
        int i = 0;
        for (Node* nit1 = fie->vs; nit1 != NULL; nit1 = (Node*)(nit1->Next))
        {
            fie->lines[i] = ((Sub_Poly_Ver*)(nit1->value));
            i++;
        }
        Sub_Poly_Ver* spv1 = (Sub_Poly_Ver*)(fie->vs->value);
        Sub_Poly_Ver* spv2 = (Sub_Poly_Ver*)(node_reverse(fie->vs)->value);
        if (fie->len > 2)
        {
            for (Node* nit1 = inner_edges; nit1 != NULL; nit1 = (Node*)(nit1->Next))
            {
                Sub_Poly_Ver** spvs = (Sub_Poly_Ver**)(nit1->value);
                if ((spvs[0] == spv1 && spvs[1] == spv2) || (spvs[0] == spv2 && spvs[1] == spv1))
                {
                    fie->is_loop = 1;
                    break;
                }
            }
        }
       
        if (fie->is_loop)
        {
            for (i = 0; i < fie->len; i++)
            {
                if (is_three_point_in_one_line(fie->lines[(i - 1 + fie->len) % fie->len]->p,
                    fie->lines[i]->p, fie->lines[(i + 1) % fie->len]->p))
                {
                    fie->marks[i] = -1;
                }
            }
        }
        else
        {
            for (i = 1; i < fie->len - 1; i++)
            {
                if (is_three_point_in_one_line(fie->lines[(i - 1 + fie->len) % fie->len]->p,
                    fie->lines[i]->p, fie->lines[(i + 1) % fie->len]->p))
                {

                    fie->marks[i] = -1;
                }
            }
        }
    }
    //printf("end fusion edge\n");
    return re;
}
static Node* get_new_inner_edges(Node* fie_n)
{
    Node* re = NULL;
    for (Node* nit = fie_n; nit != NULL; nit = (Node*)(nit->Next))
    {
        Fusion_Inner_Edges* fie = (Fusion_Inner_Edges*)(nit->value);
        Node* temp = NULL;
        for (int i = 0; i < fie->len; i++)
        {
            if (fie->marks[i] == 0)
            {
                temp = node_overlying(temp, fie->lines[i]);
            }
        }
        for (Node* nit1 = temp; nit1 != NULL; nit1 = (Node*)(nit1->Next))
        {
            if (nit1->Next != NULL)
            {
                Sub_Poly_Ver** temp1 = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * 2);
                temp1[0] = (Sub_Poly_Ver*)(nit1->value);
                temp1[1] = (Sub_Poly_Ver*)(((Node*)(nit1->Next))->value);

                re = node_overlying(re, temp1);
            }
        }
        if (fie->is_loop)
        {
            Sub_Poly_Ver** temp1 = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * 2);
            temp1[0] = (Sub_Poly_Ver*)(temp->value);
            temp1[1] = (Sub_Poly_Ver*)((node_reverse(temp))->value);
            re = node_overlying(re, temp1);
        }
        free_node(temp);
    }
    return re;
}
static void free_fusion_inner_edges_node(Node* n)
{
    for (Node* nit = n; nit != NULL; nit = (Node*)(nit->Next))
    {
        Fusion_Inner_Edges* fie = (Fusion_Inner_Edges*)(nit->value);
        SAFE_FREE(fie->marks); SAFE_FREE(fie->lines);
        free_node(fie->vs);
        free(fie);
    }
    free_node(n);
}
static void alter_triangles_from_fusion_inner_edges(Node** tris, Node* re)
{
    for (Node* nit1 = re; nit1 != NULL; nit1 = (Node*)(nit1->Next))
    {
        Fusion_Inner_Edges* fie = (Fusion_Inner_Edges*)(nit1->value);

        for (int i = 0; i < fie->len; i++)
        {
            if (fie->marks[i] == -1)
            {
                int l1 = (i - 1 + fie->len) % fie->len; int l2 = (i + 1) % fie->len;
                while (fie->marks[l1] != 0)
                {
                    l1--;
                    l1 = (l1 + fie->len) % fie->len;
                }
                while (fie->marks[l2] != 0)
                {
                    l2++;
                    l2 = l2 % fie->len;
                }
                int num = 0;
                for (Node* nit = *tris; nit != NULL; nit = (Node*)(nit->Next))
                {
                    Sub_Poly_Ver** temp = (Sub_Poly_Ver**)(nit->value);
                    int ll1 = -1, ll2 = -1;
                    for (int j = 0; j < 3; j++)
                    {
                        temp[j] == fie->lines[l1] ? (ll1 = j) : (ll1 = ll1);
                        temp[j] == fie->lines[l2] ? (ll2 = j) : (ll2 = ll2);
                    }
                    if (ll1 != -1 && ll2 != -1)
                    {
                        Sub_Poly_Ver** temp1 = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * 3);
                        memmove(temp1, temp, sizeof(Sub_Poly_Ver*) * 3);
                        temp[ll1] = fie->lines[i];
                        temp1[ll2] = fie->lines[i];
                        *tris = node_overlying(*tris, temp1);
                        num++;
                        if (num >= 2)
                        {
                            break;
                        }
                    }
                }
                fie->marks[i] = 0;
            }
        }
    }
}

Node* subdivision_of_polygon_with_edges1(double** vs, int vs_len, int* bounds, int len_bounds,
    int** inner_edges, int inner_len)
{
    Node* re = NULL;
    if (vs_len <= 3)
    {
        int* temp = (int*)malloc(sizeof(int) * 3);
        temp[0] = 0; temp[1] = 1; temp[2] = 2;
        re = node_overlying(re, temp);
        return re;
    }
    Sub_Poly_Ver** vs1 = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * vs_len);
    Sub_Poly_Ver** bounds1 = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * len_bounds);
    memset(bounds1, 0, sizeof(Sub_Poly_Ver*) * len_bounds);
    Int_RB_Tree* vs2 = (Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
    int_rb_tree_init(vs2);

    for (int i = 0; i < vs_len; i++)
    {
        vs1[i] = (Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver));
        sub_poly_ver_init(vs1[i]);
        vs1[i]->i = i;
        vs1[i]->p = vs[i];
        //printf("%d: %lf %lf %lf\n",i,vs[i][0], vs[i][1], vs[i][2]);
        // vs2->insert(vs2,i,vs1[i]);
    }
    Node* inner_edges1 = NULL;
    for (int i = 0; i < inner_len; i++)
    {
        Sub_Poly_Ver** temp = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * 2);
        temp[0] = vs1[inner_edges[i][0]]; temp[1] = vs1[inner_edges[i][1]];
       /* vs2->insert(vs2, temp[0]->i, temp[0]);
        vs2->insert(vs2, temp[1]->i, temp[1]);*/

        inner_edges1 = node_overlying(inner_edges1, temp);
    }
    //printf("begin fusion\n");
    Node* fie_n = fusion_inner_edges_to_lines(inner_edges1);

    

    Node* inner_edges2 = get_new_inner_edges(fie_n);
    //printf("inner_edges2:%d\n",node_size(inner_edges2));
    for (Node* nit=inner_edges2;nit!=NULL;nit=(Node*)(nit->Next))
    {
        Sub_Poly_Ver** temp = (Sub_Poly_Ver**)(nit->value);
        vs2->insert(vs2, temp[0]->i, temp[0]);
        vs2->insert(vs2, temp[1]->i, temp[1]);
        //printf("inner edge:%d %d\n",temp[0]->i,temp[1]->i);
    }
    //printf("end iner edges2\n");

    int* marks = (int*)malloc(sizeof(int) * len_bounds);
    memset(marks, 0, sizeof(int) * len_bounds);
    int k = 0;
    bounds1[0] = vs1[bounds[0]];
    k++;
    for (int i = 1; i < len_bounds; i++)
    {
        if (distance_of_two_points(vs1[bounds[i]]->p, bounds1[k - 1]->p, 3) < 1e-5)
        {
            if (!vertex_is_in_inner_edges(vs1[bounds[i]], inner_edges2))
            {
                //printf("mark1 :%d\n",i);
                marks[i] = -1;
            }
            else if (!vertex_is_in_inner_edges(bounds1[k - 1], inner_edges2))
            {
                int j = (i - 1);
                while (vs1[bounds[j]] != bounds1[k - 1])
                {
                    j--;
                }
                //printf("mark2 :%d\n",j);

                marks[j] = -1;
                bounds1[k - 1] = vs1[bounds[i]];
            }
            else
            {
                bounds1[k] = vs1[bounds[i]];
                k++;
            }
        }
        else if (is_three_point_in_one_line(bounds1[k - 1]->p, vs1[bounds[i]]->p,
            vs1[bounds[(i + 1) % len_bounds]]->p) && !vertex_is_in_inner_edges(vs1[bounds[i]], inner_edges2))
        {
            //printf("mark3 :%d\n",i);
            marks[i] = -1;
        }
        else
        {
            bounds1[k] = vs1[bounds[i]];
            k++;
        }
    }
    if (distance_of_two_points(bounds1[0]->p, bounds1[k - 1]->p, 3) < 1e-5)
    {
        if (!vertex_is_in_inner_edges(bounds1[0], inner_edges2))
        {
            marks[0] = -1;
            for (int i = 1; i < k; i++)
            {
                bounds1[i - 1] = bounds1[i];
            }
            k--;
        }
        else if (!vertex_is_in_inner_edges(bounds1[k - 1], inner_edges2))
        {
            k--;
        }
    }
    //k=0;
    //printf("yuan bans\n");
    Node* tris = NULL;

    for(int i=0;i<len_bounds;i++)
    {   
        if(marks[i]==-1)
        {
            int l1=(i-1+len_bounds)%len_bounds;
            while(marks[l1]!=0)
            {
                l1=(l1-1+len_bounds)%len_bounds;
            }
            int l2=(i+1)%len_bounds;
            while(marks[l2]!=0)
            {
                l2=(l2+1)%len_bounds;
            }
            //inner_edges_remove();

            if(edge_is_in_inner_edges(vs1[bounds[l1]],vs1[bounds[l2]],inner_edges2))
            {
                inner_edges2= inner_edges_remove(vs1[bounds[l1]],vs1[bounds[l2]],inner_edges2);

                Sub_Poly_Ver** temp = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*)*3);
                temp[0]=vs1[bounds[l1]];
                temp[1]=vs1[bounds[i]];
                temp[2]=vs1[bounds[l2]];
                tris=node_overlying(tris,temp);
                // bounds1[k]=vs1[bounds[i]];k++;

                marks[i]=0;
            }

        }
        // else
        // {
        //     bounds1[k]=vs1[bounds[i]];k++;
        // }
        // printf("%d\n", vs1[bounds[i]]->i);
    }
    //printf("bonds k:%d\n",k);

    double** bounds_p = (double**)malloc(sizeof(double*) * k);

    for (int i = 0; i < k; i++)
    {
        vs2->insert(vs2, bounds1[i]->i, bounds1[i]);
        bounds_p[i] = bounds1[i]->p;
        //printf("%d\n", bounds1[i]->i);
    }
   
    double normal[3]={0};
    compute_plane_normal_of_jordan_curve(bounds_p, k,normal);
    free(bounds_p);

    //vs2需要修改
    //printf("begin sub\n");

    subdivision_of_polygon_with_edges(vs2, bounds1, k, inner_edges2, &tris, normal);
    
    //printf("end sub\n");

    alter_triangles_from_fusion_inner_edges(&tris, fie_n);
    //printf("end alter inner edges\n");
    //printf("tris size:%d\n",node_size(tris));
    for (int i = 0; i < len_bounds; i++)
    {
        if (marks[i] == -1)
        {
            int l1 = (i - 1 + len_bounds) % len_bounds; int l2 = (i + 1) % len_bounds;
            while (marks[l1] != 0)
            {
                l1--;
                l1 = (l1 + len_bounds) % len_bounds;
            }
            while (marks[l2] != 0)
            {
                l2++;
                l2 = l2 % len_bounds;
            }
            for (Node* nit = tris; nit != NULL; nit = (Node*)(nit->Next))
            {
                Sub_Poly_Ver** temp = (Sub_Poly_Ver**)(nit->value);
                int ll1 = -1, ll2 = -1;
                for (int j = 0; j < 3; j++)
                {
                    temp[j] == vs1[bounds[l1]] ? (ll1 = j) : (ll1 = ll1);
                    temp[j] == vs1[bounds[l2]] ? (ll2 = j) : (ll2 = ll2);
                }
                if (ll1 != -1 && ll2 != -1)
                {
                    Sub_Poly_Ver** temp1 = (Sub_Poly_Ver**)malloc(sizeof(Sub_Poly_Ver*) * 3);
                    memmove(temp1, temp, sizeof(Sub_Poly_Ver*) * 3);
                    temp[ll1] = vs1[bounds[i]];
                    temp1[ll2] = vs1[bounds[i]];
                    tris = node_overlying(tris, temp1);
                    break;
                }
            }
            marks[i] = 0;
        }
    }


    for (Node* nit = tris; nit != NULL; nit = (Node*)(nit->Next))
    {
        int* temp = (int*)malloc(sizeof(int) * 3);
        Sub_Poly_Ver** temp1 = (Sub_Poly_Ver**)(nit->value);
        temp[0] = temp1[0]->i; temp[1] = temp1[1]->i; temp[2] = temp1[2]->i;
        re = node_overlying(re, temp);
    }
    //printf("end alter bounds\n");

    free(marks);
    // SAFE_FREE(normal);
    free_node_value(tris);
    free_node(tris);
    int_rb_tree_free(vs2);

    for (int i = 0; i < vs_len; i++)
    {
        free(vs1[i]);
    }
    free(bounds1);
    
    free_node_value(inner_edges1);
    free_node(inner_edges1);
    free_fusion_inner_edges_node(fie_n);
    free(vs1);
    return re;
}


